import java.util.Arrays;

/**
 * Created with IntelliJ IDEA
 * Description 堆模拟实现优先队列
 * User: 王杰
 * Date: 2025-06-06
 * Time: 9:23
 */
public class TestHeap {
    public int[] elem;
    public int usedSize;

    public TestHeap() {
        this.elem = new int[10];
    }

    public void initElem(int[] array) {
        for (int i = 0; i < array.length; i++) {
            this.elem[i] = array[i];
            usedSize++;
        }
    }

    // 创建大根堆
    public void createHeap() {
        for(int parent = (this.usedSize - 1 - 1) / 2; parent >= 0; parent--) {
            siftDown(parent, this.usedSize);
        }
    }

    /**
     *  向下调整建堆
     * @param parent 每颗子树调整的时候 的 起始位置
     * @param usedSize 判断 每颗子树什么时候 调整 结束
     *                 以数组的形式建堆，不以类的形式，可能会用到第二个参数，所以加上
     *  当然也存在向上调整建堆
     */
    private void siftDown(int parent, int usedSize) {
        int child = parent * 2 + 1;
        while (child < usedSize) {
            // 左右孩子最大值
            if (child + 1 < usedSize && elem[child] < elem[child + 1]) {
                child++;
            }
            if(elem[child] > elem[parent]) {
                swap(elem, child, parent);
                parent = child;
                child = parent * 2 + 1;
            }else {
                break;
            }
        }
    }

    public void offer(int val) {
        if (isFull()) {
            elem = Arrays.copyOf(elem, 2 * elem.length);
        }

        elem[usedSize] = val;
        siftUp(usedSize);
        usedSize++;
    }

    private void swap(int[] elem, int i, int j) {
        int tmp = elem[i];
        elem[i] = elem[j];
        elem[j] = tmp;
    }
    private void siftUp(int child) {
        int parent = (child - 1) / 2;
        while (parent >= 0) {
            if(elem[child] > elem[parent]) {
                swap(elem, child, parent);
                child = parent;
                parent = (child - 1) / 2;
            }else {
                break;
            }
        }

    }

    public boolean isFull() {
        return usedSize == elem.length;
    }

    public int poll() {
        if (isEmpty()) {
            return -1;
        }
        int val = elem[0];
        swap(elem, 0, usedSize - 1);
        siftDown(0 ,usedSize - 1);
        usedSize--;
        return val;
    }

    public boolean isEmpty() {
        return usedSize == 0;
    }

    // 升序
    // 时间复杂度: n * logN
    public void heapSort() {
        int end = usedSize - 1;
        while (end > 0) {
            swap(elem, 0, end);
            siftDown(0, end);
            end--;
        }
    }
}
